package com.nccs.arithmetic;

/**
 * @author xuzengsheng
 * @program nssc-parent
 * @createTime 2021-09-14- 16:48:00
 * @description 快速排序
 * 来源：https://blog.csdn.net/alan_liuyue/article/details/80740960
 */

public class QuickSort extends AbstractSortHandler {


    public QuickSort(String arithmeticName) {
        super(arithmeticName);
    }

    public static void main(String[] args) {
        new QuickSort("快速排序").execute();
    }


    @Override
    public void sort(int[] arry) {
        quickSort(arry, 0, arry.length - 1);
    }

    /**
     * 递归划分子序列
     *
     * @param arry
     * @param left
     * @param right
     */
    private void quickSort(int[] arry, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotPos = partition(arry, left, right);
        quickSort(arry, left, pivotPos - 1);
        quickSort(arry, pivotPos + 1, right);
    }


    /**
     * 划分
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partition(int[] arr, int left, int right) {
        int pivotKey = arr[left];

        while (left < right) {
            while (left < right && arr[right] >= pivotKey)
                right--;
            arr[left] = arr[right]; //把小的移动到左边
            while (left < right && arr[left] <= pivotKey)
                left++;
            arr[right] = arr[left]; //把大的移动到右边
        }
        arr[left] = pivotKey; //最后把pivot赋值到中间
        return left;
    }


}
